package com.github.hgkmail.hello.leetcode101.base;

import com.alibaba.fastjson.JSON;
import com.google.common.base.Splitter;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class CommonUtil {
    /**
     * 交换操作，是排序算法的基础操作
     */
    public static void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    //打印链表
    public static void printLinkedList(ListNode head) {
        ListNode curr=head;
        while (curr!=null) {
            System.out.print(curr.val+" ");
            curr=curr.next;
        }
        System.out.println("");
    }

    //打印二叉树：使用括号表示子树
    //格式：根(左子树)[右子树]
    private static void doPrintBinaryTree(TreeNode root) {
        if (root==null) {
            return;
        }

        System.out.print(root.val);
        if (root.left!=null) System.out.print("(");
        doPrintBinaryTree(root.left);
        if (root.left!=null)  System.out.print(")");
        if (root.right!=null) System.out.print("[");
        doPrintBinaryTree(root.right);
        if (root.right!=null) System.out.print("]");
    }

    public static void printBinaryTree(TreeNode root) {
        doPrintBinaryTree(root);
        System.out.println();
    }

    public static final String TREE_SEP=",";
    public static final String TREE_NULL="#";

    //先序遍历
    private static void doSerializeBinaryTree(TreeNode root, StringBuilder sb) {
        if (root==null) {
            sb.append(TREE_NULL).append(TREE_SEP);
            return;
        }
        sb.append(root.val).append(TREE_SEP);
        doSerializeBinaryTree(root.left, sb);
        doSerializeBinaryTree(root.right, sb);
    }

    //序列化二叉树
    public static String serializeBinaryTree(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        doSerializeBinaryTree(root, sb);
        return sb.toString();
    }

    //先序遍历
    private static TreeNode doDeserializeBinaryTree(LinkedList<String> strs) {
        if (strs.isEmpty()) {
            return null;
        }
        String first = strs.pollFirst();
        if (first.equals(TREE_NULL)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(first));
        root.left = doDeserializeBinaryTree(strs);
        root.right = doDeserializeBinaryTree(strs);

        return root;
    }

    //反序列化二叉树
    public static TreeNode deserializeBinaryTree(String str) {
        LinkedList<String> strs = new LinkedList<>();
        Splitter.on(TREE_SEP).trimResults().omitEmptyStrings().splitToStream(str).forEach(strs::offerLast);
        return doDeserializeBinaryTree(strs);
    }

    //邻接表只使用List<List<Integer>>，不要用数组。
    public static void printEdge(List<List<Integer>> graph) {
        int edgeNum=0, v;
        int sz1=graph.size(), sz2;
        for (int i = 0; i < sz1; i++) {
            sz2=graph.get(i).size();
            for (int j = 0; j < sz2; j++) {
                v=graph.get(i).get(j);
                if (v>=i) {
                    System.out.printf("%d-%d ", i, v);
                    edgeNum++;
                }
            }
        }
        System.out.println();
        System.out.println("edge num: "+edgeNum);
    }

    //从adj字符串(json)创建邻接表，格式: {{adj01,adj02}, {adj11,adj12}}
    //图论英文单词：graph、vertex、edge
    //[禁止]使用 int[][] 当邻接表来表示图！灵活性差，而且容易和邻接矩阵搞混！
    //int[][]——邻接矩阵，List<List<Integer>>——邻接表
    public static List<List<Integer>> createGraphByAdj(String json) {
        List<int[]> vertexes = JSON.parseArray(json, int[].class);
        int len=vertexes.size();
        List<List<Integer>> graph=new ArrayList<>(len);
        for (int i = 0; i < len; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < len; i++) {
            int[] adjVertexes=vertexes.get(i);
            for (int j = 0; j < adjVertexes.length; j++) {
                graph.get(i).add(adjVertexes[j]);
            }
        }
        return graph;
    }

    //获取LeetCode需要的图，LeetCode使用int[][]来表示邻接表，真是无语。。。很容易和邻接矩阵搞混，灵活性还差。
    public static int[][] getLcGraph(List<List<Integer>> graph) {
        int len=graph.size();
        int[][] g=new int[len][];
        for (int i = 0; i < len; i++) {
            List<Integer> adjVertexes=graph.get(i);
            g[i]=new int[adjVertexes.size()];
            for (int j = 0; j < g[i].length; j++) {
                g[i][j]=adjVertexes.get(j);
            }
        }
        return g;
    }

    //解析LeetCode的二维数组: [[1],[2]]
    public static int[][] parseLc2DArray(String json) {
        List<int[]> list = JSON.parseArray(json, int[].class);
        int[][] array=new int[list.size()][];
        for (int i = 0; i < array.length; i++) {
            int[] sub=list.get(i);
            array[i]=sub;
        }
        return array;
    }

    public static void print2DArray(int[][] array) {
        System.out.println(JSON.toJSON(array));
    }

    public static void main(String[] args) {
//        TreeNode a3=new TreeNode(3);
//        TreeNode a2=new TreeNode(2);
//        TreeNode a1=new TreeNode(1, a2, a3);
//        System.out.println(serializeBinaryTree(a1));

//        TreeNode a = deserializeBinaryTree("1,2,#,#,3,#,#,");
//        printBinaryTree(a);

//        printEdge("[[1,2,3],[0,2],[0,1,3],[0,2]]");
        printEdge(createGraphByAdj("[[1,3],[0,2],[1,3],[0,2]]"));
    }
}
